package leetcode

import "gitee.com/ombak/leetcode/pkg/list"

// https://leetcode.com/problems/partition-list/
// input: [1,4,3,2,5,2]  3
// output: [1,2,2,4,3,5]
func Partition(head *list.ListNode, x int) *list.ListNode {
	dummy1, dummy2 := &list.ListNode{}, &list.ListNode{}
	p1, p2 := dummy1, dummy2
	for head != nil {
		next := head.Next
		if head.Val < x {
			p1.Next = head
			p1 = p1.Next
		} else {
			p2.Next = head
			p2 = p2.Next
		}
		head = next
	}
	p1.Next = dummy2.Next
	p2.Next = nil
	return dummy1.Next
}
